package tree

// 前缀树（字典树）Trie树
// 这里使用的都是小写英文字符
// 关于前缀树的删除，有一种前缀树世纪路了节点的使用次数的，而这种树没有的，所以删除的话会导致别的前缀也删除。
type TrieTree struct {
	Children [26]*TrieTree
	CoverCounter int //用于记录当前节点覆盖次数，在删除时，覆盖次数为0才可以删除当前节点，否则只是自减1, (存在公用节点的关系，必须记录)
	IsEnd	bool
}

func NewTrieTree()*TrieTree{
	return new(TrieTree)
}

func (t *TrieTree)Insert(word string) {
	node := t
	for _, ch := range word {
		ch -= 'a'
		if node.Children[ch] == nil {
			node.Children[ch] = NewTrieTree()
			node.Children[ch].CoverCounter ++
		}
		node = node.Children[ch]
	}
	node.IsEnd = true
}

func (t *TrieTree)SearchPrefix(prefix string)*TrieTree{
	node := t 
	for _, ch := range prefix {
		ch -= 'a'
		if node.Children[ch] == nil {
			return nil
		}
		node = node.Children[ch]
	}
	return node
} 

// word 是否存在于字典中
func (t *TrieTree)Search(word string)bool{
	node := t.SearchPrefix(word)
	return node !=nil && node.IsEnd 
}

// 是否有前缀
func (t *TrieTree)StartsWith(prefix string)bool {
	return t.SearchPrefix(prefix) != nil
}

// 删除单词（前缀一般是不轻易删除的）
// 删除前缀基本套路也差不多
func (t *TrieTree)DeleteWord(word string){
	// 查询word 是否在其中
	if t.Search(word){
		node := t 
		for _, ch := range word {
			ch -= 'a'
			//不用检测children节点是否为空
			if node.Children[ch].CoverCounter == 1 {
				//进入这里表示只有当前 word 使用该节点，和当前节点的子树，所以直接置空退出即可
				node.Children[ch] = nil
				return
			}else{
				node.Children[ch].CoverCounter -- 
			}
			node = node.Children[ch]
		}
	}
}